Low-density parity-check (LDPC) codes, like other codes such as Hamming codes, use a number of bits for a given message word. Each parity check covers a different set of the message bits and the parity checks overlap so that any one message bit is covered by more than one parity check. This means that where there are a limited number of errors it is possible to identify the location of an error. LDPC codes are characterized by a parity check matrix, denoted H, which has a row for each parity check and a column for each bit in the total code word. For LCPC codes, these parity check matrices are very large and sparse (i.e. they comprise mostly zeros with only a few ones) which results in very long code words.
The parity check matrices, H, may also be represented in the form of a Tanner graph and FIG. 1 shows an example parity check matrix 102 and corresponding Tanner graph 104. The Tanner graph 104 shows bit nodes 106 and check nodes 108 and the connections (or edges) between them. There is one bit node for each bit in the code word (and these correspond to the columns in the parity check matrix 102) and one check node for each parity check (and these correspond to the rows in the parity check matrix 102).
LDPC codes are typically decoded using soft-in-soft-out methods in which a previous stage passes information into the decoder that describes the estimated value (1 or 0) for each bit and a confidence value associated with the estimate. The confidence value may be in the form of a Log-Likelihood Ratio (LLR). The decoder outputs information in the same form (i.e. estimated value and confidence associated with the estimate). The decoder uses an iterative message passing algorithm based on belief propagation to perform the decoding. According to an example of such an algorithm, the bit nodes tells the connected check nodes their current LLR estimate and using this information the check nodes perform their parity checks and provide information back to each connected bit node regarding the likelihood that the associated bit is a ‘1’. On receipt of the updated information, the bit nodes combine the values they receive from all the connected check nodes. The method is then repeated, with bit nodes providing updated LLRs to check nodes, although the value passed to any check node from a bit node may be different, such that a check node receives only ‘new’ information which indicates how the other connected check nodes modified the LLR in the previous iteration (i.e. a check node receives information relating to changes made by to the LLR by all the other connected check nodes except for itself). This method is an example of Two-Pass Message Passing (TPMP) and the decoding may be made more efficient by combining the two passes and the result may be a Merged-Schedule Messaging Passing (MSMP) algorithm.
Using MSMP the current LLR estimate for each bit node is used to calculate and store a value which represents the check node to bit node message and once a value has been calculated it is used to update a temporary variable which is the running total of LLR updates for each bit node. Once all check nodes have been processed (and their check node to bit node messages used to update the running totals), the running total is used to update a stored value of the LLR (the current LLR estimate) for each bit. As before, this method is then repeated.
There are many applications for LDPC codes as they have been found to provide a reliable and efficient method for transmitting data over a noisy transmission channel. Examples include use in many digital television standards (whether for terrestrial, satellite, cable or mobile use), such as DVB-T2, DVB-S2 and DVB-C2, and other wireless standards, such as WiMAX™ and some WiFi™ variants.
The embodiments described below are not limited to implementations which solve any or all of the disadvantages of known LDPC decoders.